SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Unrooted binary tree</title>

</head>

Unrooted binary tree

</h1>

</header>

In mathematics and computer science, an unrooted binary tree is an <a href="Free_tree" class="mw-redirect" title="Free tree">unrooted tree</a> in which each <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertex</a> has either one or three neighbors.

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

A <a href="Free_tree" class="mw-redirect" title="Free tree">free tree</a> or unrooted tree is a <a href="Connected_graph" class="mw-redirect" title="Connected graph">connected</a> <a href="Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a> with no <a href="Cycle_(graph_theory)" title="Cycle (graph theory)">cycles</a>. The vertices with one neighbor are the leaves of the tree, and the remaining vertices are the internal nodes of the tree. The <a href="Degree_(graph_theory)" title="Degree (graph theory)">degree</a> of a vertex is its number of neighbors; in a tree with more than one node, the leaves are the vertices of degree one. An unrooted binary tree is a free tree in which all internal nodes have degree exactly three.

In some applications it may make sense to distinguish subtypes of unrooted binary trees: a <a href="Planar_graph" title="Planar graph">planar embedding</a> of the tree may be fixed by specifying a cyclic ordering for the edges at each vertex, making it into a <a href="Ordered_tree" class="mw-redirect" title="Ordered tree">plane tree</a>. In computer science, binary trees are often rooted and ordered when they are used as <a href="Data_structure" title="Data structure">data structures</a>, but in the applications of unrooted binary trees in <a href="Hierarchical_clustering" title="Hierarchical clustering">hierarchical clustering</a> and <a href="Evolutionary_tree" class="mw-redirect" title="Evolutionary tree">evolutionary tree</a> reconstruction, unordered trees are more common.<a href="#cite_note-f84-1">[1]</a>

Additionally, one may distinguish between trees in which all vertices have distinct labels, trees in which the leaves only are labeled, and trees in which the nodes are not labeled. In an unrooted binary tree with n leaves, there will be n − 2 internal nodes, so the labels may be taken from the set of integers from 1 to 2n − 1 when all nodes are to be labeled, or from the set of integers from 1 to n when only the leaves are to be labeled.<a href="#cite_note-f84-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Related_structures">Related structures</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Rooted_binary_trees">Rooted binary trees</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Rooted_binary_tree" class="mw-redirect" title="Rooted binary tree">Rooted binary tree</a></div>

An unrooted binary tree T may be transformed into a full rooted <a href="Binary_tree" title="Binary tree">binary tree</a> (that is, a rooted tree in which each non-leaf node has exactly two children) by choosing a root edge e of T, placing a new root node in the middle of e, and directing every edge of the resulting subdivided tree away from the root node. Conversely, any full rooted binary tree may be transformed into an unrooted binary tree by removing the root node, replacing the path between its two children by a single undirected edge, and suppressing the orientation of the remaining edges in the graph. For this reason, there are exactly 2n −3 times as many full rooted binary trees with n leaves as there are unrooted binary trees with n leaves.<a href="#cite_note-f84-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Hierarchical_clustering">Hierarchical clustering</h3></div>

A <a href="Hierarchical_clustering" title="Hierarchical clustering">hierarchical clustering</a> of a collection of objects may be formalized as a <a href="Maximal_element" class="mw-redirect" title="Maximal element">maximal</a> <a href="Family_of_sets" title="Family of sets">family of sets</a> of the objects in which no two sets cross. That is, for every two sets S and T in the family, either S and T are disjoint or one is a subset of the other, and no more sets can be added to the family while preserving this property. If T is an unrooted binary tree, it defines a hierarchical clustering of its leaves: for each edge (u,v) in T there is a cluster consisting of the leaves that are closer to u than to v, and these sets together with the empty set and the set of all leaves form a maximal non-crossing family. Conversely, from any maximal non-crossing family of sets over a set of n elements, one can form a unique unrooted binary tree that has a node for each triple (A,B,C) of disjoint sets in the family that together cover all of the elements.<a href="#cite_note-2">[2]</a>

<div class="mw-heading mw-heading3"><h3 id="Evolutionary_trees">Evolutionary trees</h3></div>

According to simple forms of the <a href="Theory_of_evolution" class="mw-redirect" title="Theory of evolution">theory of evolution</a>, the history of life can be summarized as a <a href="Phylogenetic_tree" title="Phylogenetic tree">phylogenetic tree</a> in which each node describes a species, the leaves represent the species that exist today, and the edges represent ancestor-descendant relationships between species. This tree has a natural orientation from ancestors to descendants, and a root at the <a href="Common_ancestor" class="mw-redirect" title="Common ancestor">common ancestor</a> of the species, so it is a rooted tree. However, some methods of reconstructing binary trees can reconstruct only the nodes and the edges of this tree, but not their orientations.

For instance, <a href="Cladistics" title="Cladistics">cladistic methods</a> such as <a href="Maximum_parsimony" title="Maximum parsimony">maximum parsimony</a> use as data a set of binary attributes describing features of the species. These methods seek a tree with the given species as leaves in which the internal nodes are also labeled with features, and attempt to minimize the number of times some feature is present at only one of the two endpoints of an edge in the tree. Ideally, each feature should only have one edge for which this is the case. Changing the root of a tree does not change this number of edge differences, so methods based on parsimony are not capable of determining the location of the tree root and will produce an unrooted tree, often an unrooted binary tree.<a href="#cite_note-3">[3]</a>

Unrooted binary trees also are produced by methods for inferring evolutionary trees based on quartet data specifying, for each four leaf species, the unrooted binary tree describing the evolution of those four species, and by methods that use <a href="Quartet_distance" title="Quartet distance">quartet distance</a> to measure the distance between trees.<a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading3"><h3 id="Branch-decomposition">Branch-decomposition</h3></div>

Unrooted binary trees are also used to define <a href="Branch-decomposition" title="Branch-decomposition">branch-decompositions</a> of graphs, by forming an unrooted binary tree whose leaves represent the edges of the given graph. That is, a branch-decomposition may be viewed as a hierarchical clustering of the edges of the graph. Branch-decompositions and an associated numerical quantity, branch-width, are closely related to <a href="Treewidth" title="Treewidth">treewidth</a> and form the basis for efficient <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> algorithms on graphs.<a href="#cite_note-rs91-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Enumeration">Enumeration</h2></div>

Because of their applications in hierarchical clustering, the most natural <a href="Graph_enumeration" title="Graph enumeration">graph enumeration</a> problem on unrooted binary trees is to count the number of trees with n labeled leaves and unlabeled internal nodes. An unrooted binary tree on n labeled leaves can be formed by connecting the nth leaf to a new node in the middle of any of the edges of an unrooted binary tree on n − 1 labeled leaves. There are 2n − 5 edges at which the nth node can be attached; therefore, the number of trees on n leaves is larger than the number of trees on n − 1 leaves by a factor of 2n − 5. Thus, the number of trees on n labeled leaves is the <a href="Double_factorial" title="Double factorial">double factorial</a>

<mfrac>

<mrow>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (2n-5)!!={\frac {(2n-4)!}{(n-2)!2^{n-2}}}.}</annotation>

</semantics>

</math><img src="./bf0092d1eb576de80e60b8a6c74eb4902b0077c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:26.58ex; height:6.676ex;" alt="{\displaystyle (2n-5)!!={\frac {(2n-4)!}{(n-2)!2^{n-2}}}.}" loading="lazy"><a href="#cite_note-6">[6]</a></dd></dl>

The numbers of trees on 2, 3, 4, 5, ... labeled leaves are

<dl><dd>1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, ... (sequence <a href="https://oeis.org/A001147" class="extiw external" title="oeis:A001147">A001147</a> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>).</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Fundamental_Equalities">Fundamental Equalities</h2></div>

The leaf-to-leaf path-length on a fixed Unrooted Binary Tree (UBT) T encodes the number of edges belonging to the unique path in T connecting a given leaf to another leaf. For example, by referring to the UBT shown in the image on the right, the path-length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1,2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1,2}}</annotation>

</semantics>

</math><img src="./0b14d10917ed5ae930df558c00304220540c1033.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:3.592ex; height:2.343ex;" alt="{\displaystyle p_{1,2}}" loading="lazy"> between the leaves 1 and 2 is equal to 2 whereas the path-length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1,3}}</annotation>

</semantics>

</math><img src="./8e854c5eaa0ea97bdc63e9d180ab5ed74d587ca7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:3.592ex; height:2.343ex;" alt="{\displaystyle p_{1,3}}" loading="lazy"> between the leaves 1 and 3 is equal to 3. The path-length sequence from a given leaf on a fixed UBT T encodes the lengths of the paths from the given leaf to all the remaining ones. For example, by referring to the UBT shown in the image on the right, the path-length sequence from the leaf 1 is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}=(p_{1,2},p_{1,3},p_{1,4})=(2,3,3)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}=(p_{1,2},p_{1,3},p_{1,4})=(2,3,3)}</annotation>

</semantics>

</math><img src="./5afffbee43fe321821a45365a1c40835627f288f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:30.261ex; height:3.009ex;" alt="{\displaystyle p_{1}=(p_{1,2},p_{1,3},p_{1,4})=(2,3,3)}" loading="lazy">. The set of path-length sequences associated to the leaves of T is usually referred to as the path-length sequence collection of T <a href="#cite_note-On_the_Balanced_Minimum_Evolution_P-7">[7]</a>

.

Daniele Catanzaro, Raffaele Pesenti and <a href="Laurence_Wolsey" title="Laurence Wolsey">Laurence Wolsey</a> showed<a href="#cite_note-On_the_Balanced_Minimum_Evolution_P-7">[7]</a> that the path-length sequence collection encoding a given UBT with n leaves must satisfy specific equalities, namely

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i,i}=0}</annotation>

</semantics>

</math><img src="./d0968d1f60e58f45286621eff50b232aa97ecb1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:7.344ex; height:2.843ex;" alt="{\displaystyle p_{i,i}=0}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in [1,n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in [1,n]}</annotation>

</semantics>

</math><img src="./187aac10c25cda8894bbfd346ad5f8349260a7cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.528ex; height:2.843ex;" alt="{\displaystyle i\in [1,n]}" loading="lazy"></li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i,j}=p_{j,i}}</annotation>

</semantics>

</math><img src="./452fff21469bfeef2cfde7251fb107dd97c575d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:9.396ex; height:2.343ex;" alt="{\displaystyle p_{i,j}=p_{j,i}}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i,j\in [1,n]:i\neq j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i,j\in [1,n]:i\neq j}</annotation>

</semantics>

</math><img src="./7a9db347e4144107ede072ed0c5bcd8b89a054c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.316ex; height:2.843ex;" alt="{\displaystyle i,j\in [1,n]:i\neq j}" loading="lazy"></li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i,j}\leq p_{i,k}+p_{k,j}}</annotation>

</semantics>

</math><img src="./ad78ee3f9360fd5ce4aa618e82d2fc275da746f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:15.808ex; height:2.676ex;" alt="{\displaystyle p_{i,j}\leq p_{i,k}+p_{k,j}}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i,j,k\in [1,n]:i\neq j\neq k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i,j,k\in [1,n]:i\neq j\neq k}</annotation>

</semantics>

</math><img src="./9588c79784f1dd0092f6f6bd7025db99f0f68447.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.871ex; height:2.843ex;" alt="{\displaystyle i,j,k\in [1,n]:i\neq j\neq k}" loading="lazy"></li>

</mrow>

</mrow>

</munderover>

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{j=1}^{n}1/2^{p_{i,j}}=1/2}</annotation>

</semantics>

</math><img src="./99cecaea04b8f8894f55b85a4de085acd9efa49e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:16.421ex; height:7.176ex;" alt="{\displaystyle \sum _{j=1}^{n}1/2^{p_{i,j}}=1/2}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in [1,n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in [1,n]}</annotation>

</semantics>

</math><img src="./187aac10c25cda8894bbfd346ad5f8349260a7cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.528ex; height:2.843ex;" alt="{\displaystyle i\in [1,n]}" loading="lazy"> (which is an adaptation of the <a href="Kraft%E2%80%93McMillan_inequality" title="Kraft–McMillan inequality">Kraft–McMillan inequality</a>)</li>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}p_{i,j}/2^{p_{i,j}}=2n-3}</annotation>

</semantics>

</math><img src="./22081e99955067e64d48df782a48c552219ff119.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:25.177ex; height:7.176ex;" alt="{\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}p_{i,j}/2^{p_{i,j}}=2n-3}" loading="lazy">, also referred to as the phylogenetic manifold.<a href="#cite_note-On_the_Balanced_Minimum_Evolution_P-7">[7]</a></li></ul>

These equalities are proved to be necessary and independent for a path-length collection to encode an UBT with n leaves.<a href="#cite_note-On_the_Balanced_Minimum_Evolution_P-7">[7]</a> It is currently unknown whether they are also sufficient.

<div class="mw-heading mw-heading2"><h2 id="Alternative_names">Alternative names</h2></div>

Unrooted binary trees have also been called free binary trees,<a href="#cite_note-8">[8]</a> cubic trees,<a href="#cite_note-9">[9]</a> ternary trees<a href="#cite_note-rs91-5">[5]</a> and unrooted ternary trees.<a href="#cite_note-10">[10]</a> However, the "free binary tree" name has also been applied to unrooted trees that may have degree-two nodes<a href="#cite_note-11">[11]</a> and to rooted binary trees with unordered children,<a href="#cite_note-12">[12]</a> and the "ternary tree" name is more frequently used to mean a <a href="Ternary_tree" title="Ternary tree">rooted tree with three children per node</a>.

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width reflist-columns-2">

<li id="cite_note-f84-1">^ <a href="#cite_ref-f84_1-0">a</a> <a href="#cite_ref-f84_1-1">b</a> <a href="#cite_ref-f84_1-2">c</a> <a href="#CITEREFFurnas1984">Furnas (1984)</a>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> See e.g. <a href="#CITEREFEppstein2009">Eppstein (2009)</a> for the same correspondence between clusterings and trees, but using rooted binary trees instead of unrooted trees and therefore including an arbitrary choice of the root node.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="#CITEREFHendyPenny1989">Hendy & Penny (1989)</a>.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <a href="#CITEREFSt._JohnWarnowMoretVawterd2003">St. John et al. (2003)</a>.

</li>

<li id="cite_note-rs91-5">^ <a href="#cite_ref-rs91_5-0">a</a> <a href="#cite_ref-rs91_5-1">b</a> <a href="#CITEREFRobertsonSeymour1991">Robertson & Seymour (1991)</a>.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <a href="#CITEREFBaldingBishopCannings2007">Balding, Bishop & Cannings (2007)</a>.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCatanzaroPesentiWolsey2020" class="citation journal cs1">Catanzaro D, Pesenti R, Wolsey L (2020). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disopt.2020.100570">"On the Balanced Minimum Evolution Polytope"</a>. Discrete Optimization. 36: 100570. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disopt.2020.100570">10.1016/j.disopt.2020.100570</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2078.1%2F230413">2078.1/230413</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:213389485">213389485</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <a href="#CITEREFCzumajGibbons1996">Czumaj & Gibbons (1996)</a>.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <a href="#CITEREFExoo1996">Exoo (1996)</a>.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <a href="#CITEREFCilibrasiVitanyi2006">Cilibrasi & Vitanyi (2006)</a>.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <a href="#CITEREFHararyPalmerRobinson1992">Harary, Palmer & Robinson (1992)</a>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <a href="#CITEREFPrzytyckaLarmore1994">Przytycka & Larmore (1994)</a>.

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFBaldingBishopCannings2007" class="citation cs2">Balding, D. J.; Bishop, Martin J.; Cannings, Christopher (2007), Handbook of Statistical Genetics, vol. 1 (3rd ed.), Wiley-Interscience, p. 502, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-470-05830-5</bdi></cite>.</li>

<li><cite id="CITEREFCilibrasiVitanyi2006" class="citation arxiv cs1">Cilibrasi, Rudi; Vitanyi, Paul M.B. (2006). "A new quartet tree heuristic for hierarchical clustering". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0606048">cs/0606048</a>.</cite>.</li>

<li><cite id="CITEREFCzumajGibbons1996" class="citation cs2">Czumaj, Artur; Gibbons, Alan (1996), "Guthrie's problem: new equivalences and rapid reductions", Theoretical Computer Science, 154 (1): 3–22, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2895%2900126-3">10.1016/0304-3975(95)00126-3</a></cite>.</li>

<li><cite id="CITEREFEppstein2009" class="citation cs2">Eppstein, David (2009), "Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition", ACM Transactions on Algorithms, 5 (3): 1–24, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs.CG/0604034">cs.CG/0604034</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1541885.1541890">10.1145/1541885.1541890</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2434">2434</a></cite>.</li>

<li><cite id="CITEREFExoo1996" class="citation cs2">Exoo, Geoffrey (1996), <a rel="nofollow" class="external text" href="http://www.combinatorics.org/Volume_3/PDFFiles/v3i1r30.pdf">"A simple method for constructing small cubic graphs of girths 14, 15, and 16"</a> (PDF), Electronic Journal of Combinatorics, 3 (1): R30, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.37236%2F1254">10.37236/1254</a></cite>.</li>

<li><cite id="CITEREFFurnas1984" class="citation cs2">Furnas, George W. (1984), "The generation of random, binary unordered trees", Journal of Classification, 1 (1): 187–233, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01890123">10.1007/BF01890123</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:121121529">121121529</a></cite>.</li>

<li><cite id="CITEREFHararyPalmerRobinson1992" class="citation cs2"><a href="Frank_Harary" title="Frank Harary">Harary, Frank</a>; Palmer, E.M.; Robinson, R.W. (1992), <a rel="nofollow" class="external text" href="http://www.cs.uga.edu/~rwr/publications/binary.pdf">"Counting free binary trees admitting a given height"</a> (PDF), Journal of Combinatorics, Information, and System Sciences, 17: 175–181</cite>.</li>

<li><cite id="CITEREFHendyPenny1989" class="citation cs2">Hendy, Michael D.; Penny, David (1989), "A framework for the quantitative study of evolutionary trees", Systematic Biology, 38 (4): 297–309, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2992396">10.2307/2992396</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2992396">2992396</a></cite></li>

<li><cite id="CITEREFPrzytyckaLarmore1994" class="citation cs2"><a href="Teresa_Przytycka" title="Teresa Przytycka">Przytycka, Teresa M.</a>; <a href="Lawrence_L._Larmore" title="Lawrence L. Larmore">Larmore, Lawrence L.</a> (1994), "The optimal alphabetic tree problem revisited", Proc. 21st International Colloquium on Automata, Languages and Programming (ICALP '94), Lecture Notes in Computer Science, vol. 820, Springer-Verlag, pp. 251–262, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-58201-0_73">10.1007/3-540-58201-0_73</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-58201-4</bdi></cite>.</li>

<li><cite id="CITEREFRobertsonSeymour1991" class="citation cs2"><a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Robertson, Neil</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, Paul D.</a> (1991), "Graph minors. X. Obstructions to tree-decomposition", Journal of Combinatorial Theory, 52 (2): 153–190, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0095-8956%2891%2990061-N">10.1016/0095-8956(91)90061-N</a></cite>.</li>

<li><cite id="CITEREFSt._JohnWarnowMoretVawterd2003" class="citation cs2">St. John, Katherine; <a href="Tandy_Warnow" title="Tandy Warnow">Warnow, Tandy</a>; <a href="Bernard_Moret" title="Bernard Moret">Moret, Bernard M. E.</a>; Vawterd, Lisa (2003), <a rel="nofollow" class="external text" href="http://infoscience.epfl.ch/record/97874/files/jalgs.pdf">"Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining"</a> (PDF), Journal of Algorithms, 48 (1): 173–193, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0196-6774%2803%2900049-X">10.1016/S0196-6774(03)00049-X</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5550338">5550338</a></cite>.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-02" href="https://en.wikipedia.org/wiki/?title=Unrooted_binary_tree&oldid=1293527137">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>